iT邦幫忙

0

##使用BigO來衡量程式碼的時間複雜度(time complexity)是很重要的一件事情,接下來讓我們來學習吧
以下為閱讀[https://pjchender.blogspot.com/2017/09/big-o-notation-time-complexity.html] PJ老師的閱後心得,並且搭配JavaScript資料結構與演算法!!!

  • BigO使用Worst case

https://ithelp.ithome.com.tw/upload/images/20210514/20130419dZwLugTprF.png


BigO(1)

只輸出該array的index值0、1,即為常數1

function BigO(array){
    console.log(array[0])
    console.log(array[1])
}
BigO([0,1,2,3,4,5])
//0
//1

BigO(n)

輸出n即線性輸出,若輸入10000次即輸出10000次

function BigO(array){
   for(let i=0; i<array.length; i++){
       console.log(array[i])
   }
}
BigO([0,1,2,3,4,5])
// 0
// 1
// 2
// 3
// 4
// 5

BigO(n^2)

輸出n即為平方,要特別注意BigO(n^2)是很差的算法了!!!

function BigO(array){
   for(let i=0; i<array.length; i++){
       for(let j=0; j<array.length; j++){
           console.log(array[j])
       }
   }
}
BigO([0,1])
// 0
// 1
// 0
// 1


BigO(log n)

雖然輸入是線性,但因為每次都對半砍,所以為BigO(logn)

let array1 = [1,3,5,7,9,11]

function BigO(array, key){
    let min = 0 
    let max = array.length -1
    while(min <= max){
        let middle = Math.floor((min + max) /2)
        
        if(array[middle] > key) {
            max = array[middle -1]
        }else if(array[middle] < key){
            min = array[middle +1]
        }else{
            return middle
        }
    }
}
console.log(BigO(array1, 5 ))
//index為2

圖片
  直播研討會
圖片
{{ item.channelVendor }} {{ item.webinarstarted }} |
{{ formatDate(item.duration) }}
直播中

尚未有邦友留言

立即登入留言